/*
 * Copyright (C), 2015-2018
 * FileName: Solution014
 * Author:   zhao
 * Date:     2018/7/23 22:52
 * Description: 第十四题
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.hundredone;

/**
 * 〈一句话功能简述〉<br>
 * 〈第十四题〉
 *
 * @author zhao
 * @date 2018/7/23 22:52
 * @since 1.0.0
 */
public class Solution070 {
  /*********************
   * 题目
   *
   * 假设你正在爬楼梯。需要 n 步你才能到达楼顶。
   *
   * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
   *
   * 注意：给定 n 是一个正整数。
   *
   * 示例 1：
   *
   * 输入： 2
   * 输出： 2
   * 解释： 有两种方法可以爬到楼顶。
   * 1.  1 步 + 1 步
   * 2.  2 步
   * 示例 2：
   *
   * 输入： 3
   * 输出： 3
   * 解释： 有三种方法可以爬到楼顶。
   * 1.  1 步 + 1 步 + 1 步
   * 2.  1 步 + 2 步
   * 3.  2 步 + 1 步
   */

  /**************************************
   * 我的做法
   * 超过23.12%的测试案例
   *  没做出来，失败
   * 我的想法
   * 从一个
   *
   * 设置一个全局变量
   *
   * ***********************************/
  public int climbStairs(int n) {
    if (CommonValue.NOT_ANSWER) {
      return better2(n);
    }

    recuClimbStairs(n);
    return result;
  }

  int result = 0;

  private int recuClimbStairs(int n) {
    if (n <= 0) {
      result++;
      return result;
    }

    if (n - 2 >= 0) {
      recuClimbStairs(n - 2);
    }
    recuClimbStairs(n - 1);
    return result;
  }

  /**************************************
   * 比我好的答案
   * 这个答案也是会超时的
   * 第二次做了，我还是以这个方式进行解答，没有理解答案
   * ***********************************/
  public int better(int n) {
    if (n <= 3) {
      return n;
    }
    return better(n - 1) + better(n - 2);
  }

  public int better2(int n) {
    if (n <= 3) {
      return n;
    } else {
      int[] arr = new int[n + 1];
      arr[0] = 0;
      arr[1] = 1;
      arr[2] = 2;
      for (int i = 3; i < n + 1; i++) {
        arr[i] = arr[i - 1] + arr[i - 2];
      }
      return arr[n];
    }

  }

}